#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣1011. 在 D 天内送达包裹的能力
// 【难度】中等
// 【提交】2025.9.25 https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/submissions/666020100/
// 【标签】二分查找；贪心算法

const auto _ = std::cin.tie(nullptr)->sync_with_stdio(false);
#define LC_HACK
#ifdef LC_HACK
const auto __ = []() {
    struct ___ {
        static void _() { std::ofstream("display_runtime.txt") << 0 << '\n'; }
    };
    std::atexit(&___::_);
    return 0;
}();
#endif

class Solution_LC1011 {
public:
    bool find(vector<int>& ws, int t, int d) {
        int n = ws.size();
        int cnt = 1;
        for (int i = 1, sum = ws[0]; i < n; sum = 0, ++cnt) {
            while (i < n && sum + ws[i] <= t) {
                sum += ws[i];
                i++;
            }
        }
        return cnt - 1 <= d;
    }
    
    int shipWithinDays(vector<int>& ws, int d) {
        int min_cap = 0, sum = 0;
        for (auto& w : ws) {
            min_cap = max(min_cap, w);
            sum += w;
        }
        //int min = (accumulate(ws.begin(),ws.end(),0))/ws.size(),
        //sum = accumulate(ws.begin(),ws.end(),0);
        int l = min_cap, r = sum;
        while (l < r) {
            int mid = (l + r) >> 1; 
            find(ws, mid, d) ? r = mid : l = mid + 1;
        }
        return r;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个整数数组ws表示每个包裹的重量，和一个整数d表示需要在d天内完成运输。
 * 要求找到最小的运载能力，使得按照顺序装载包裹时，能在d天内完成运输。
 * 模型：二分查找+贪心验证，通过二分法确定可能的最小运载能力。
 * 
 * 二、标准解法状态设计
 * 1. 使用二分查找确定可能的运载能力，范围是[最大单件重量, 总重量]。
 * 2. 对于每个候选的运载能力mid，使用贪心算法验证是否能在d天内完成运输。
 * 3. 贪心策略是按照顺序装载包裹，尽可能多地装载直到超过当前运载能力。
 * 
 * 三、你的实现思路
 * 使用二分查找法确定最小可能的运载能力，对于每个候选值使用贪心算法进行验证。
 * 使用位运算优化了二分查找的中间值计算。
 * 
 * 四、逐行注释（带细节提醒）
 * bool find(vector<int>& ws, int t, int d) { // 检查函数
 *     int n = ws.size();
 *     int cnt = 1; // 天数计数
 *     for (int i = 1, sum = ws[0]; i < n; sum = 0, ++cnt) {
 *         while (i < n && sum + ws[i] <= t) { // 尽可能多地装载
 *             sum += ws[i];
 *             i++;
 *         }
 *     }
 *     return cnt - 1 <= d; // 检查是否在d天内完成
 * }
 * 
 * int shipWithinDays(vector<int>& ws, int d) {
 *     int min_cap = 0, sum = 0;
 *     for (auto& w : ws) { // 计算最小和最大可能容量
 *         min_cap = max(min_cap, w);
 *         sum += w;
 *     }
 *     
 *     int l = min_cap, r = sum; // 二分查找边界
 *     while (l < r) {
 *         int mid = (l + r) >> 1; // 使用位运算计算中间值
 *         find(ws, mid, d) ? r = mid : l = mid + 1; // 根据检查结果更新边界
 *     }
 *     return r; // 返回最小可行容量
 * }
 * 
 * 五、正确性证明
 * 二分查找可以正确找到满足条件的最小运载能力，因为如果某个容量t可行，那么所有更大的容量也可行。
 * 贪心策略的正确性基于：为了最小化运载能力，应该尽可能多地装载货物，但不超过容量限制。
 * 
 * 六、复杂度
 * 时间：O(n log S)，其中n是包裹数量，S是总重量。
 *     二分查找需要O(log S)次迭代，每次验证需要O(n)。
 * 空间：O(1)，只使用了常数级别的额外空间。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 算法效率高，能够处理较大规模的数据；
 *   - 思路清晰，结合了二分查找和贪心算法的优点；
 *   - 使用位运算优化了计算效率。
 * 缺点：
 *   - find函数中的循环逻辑可能不够直观；
 *   - 变量命名可以更明确（如使用capacity代替t）；
 *   - 调试代码可能影响在线评测。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (ws.empty() || d <= 0) return -1;
 * 2. 使用更明确的变量名（如 capacity 代替 t，weights 代替 ws）来增强可读性；
 * 3. 对于在线评测，可以移除调试代码；
 * 4. 可以优化find函数的实现，使其更易理解。
 * 
 * 九、一句话总结
 * 通过二分查找确定最小可能的运载能力，并结合贪心算法进行验证，你的实现高效且准确，
 * 但需要注意代码可读性和调试代码的影响。
 */